package com.demo.study.algorithm.sorts;

import com.demo.study.utils.ArrayUtil;

import static com.demo.study.utils.ArrayUtil.swap;

/**
 * 选择排序
 *
 * @author Baymax
 * @since 2024-08-07
 */
public class B02_SelectSort {
    public static void main(String[] args) {
        int[] nums = ArrayUtil.intRandomArray();
        ArrayUtil.printArray(nums);
        selectSort(nums);
        ArrayUtil.printArray(nums);

        nums = ArrayUtil.intRandomArray();
        ArrayUtil.printArray(nums);
        sort(nums);
        ArrayUtil.printArray(nums);
    }

    /**
     * 选择排序：从未排序的集合中，选择最大的一位，放到最右侧已排序集合的最左侧
     */
    public static void selectSort(int[] nums) {
        // 1.选择轮数：n.length - 1，最后一个元素不需要再排了
        // 2.交换的索引位置，初始n.length - 1（最右边），递减
        for (int right = nums.length - 1; right > 0; right--) {
            int maxIndex = right; // 假设右边的最大
            for (int i = 0; i < right; i++) {
                if (nums[i] > nums[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(nums, maxIndex, right);
        }
    }

    /**
     * 选择排序：在未排序的集合中，找到最小的元素，放到左侧已排序集合的最后一位
     * 时间复杂度：O(n^2)
     */
    public static void sort(int[] nums) {
        // 外循环：区间为[i, n -1]，最后一个元素不需要排
        for (int i = 0; i < nums.length - 1; i++) {
            int minIndex = i; // 假设最左边的最小
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            swap(nums, i, minIndex);
        }
    }
}
